package Top101K;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;

/**
 * @Author quan
 * @Description
 *
 * @Date 2023/11/20 10:01
 */
public class BM50_TwoSum {
    public static void main(String[] args) {
        int[] arr = {3,2,4};
        int[] res = twoSum(arr,6);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }
    }

    /**
     * 给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
     * （注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
     * @param numbers [20,70,110,150]
     * @param target  90
     * @return [1,2]
     */
//    public static int[] twoSum (int[] numbers, int target) {
//        // write code here
//        // 暴力解法：双层for循环 - 复杂度太高,加if降低复杂度
//        int[] res = new int[2];
//        for (int i = 0; i < numbers.length; i++) {
//            if(numbers[i] > target){
//                continue;
//            }
//            for (int j = i+1; j < numbers.length; j++) {
//                if(numbers[i] + numbers[j] == target){
//                    res[0] = Math.min(i+1,j+1);
//                    res[1] = Math.max(i+1,j+1);
//                    return res;
//                }
//            }
//        }
//        return res;
//    }

    /**
     * 解法2：这里面说的是找到两个和为 target 的数组下标，那是不是可以理解为 找到数组中 值为 target - nums[i] 的数值下标，而这种思路就可以想到使用 hash 表来实现。
     * @param numbers [20,70,110,150]
     * @param target 90
     * @return [1,2]
     */
    public static int[] twoSum (int[] numbers, int target) {
        //1-构建一个hash表
        //2-遍历数组元素为nums[i]，如果哈希表中没有target-nums[i]的值，说明之前遍历的元素中没有对应的值，我们将它加入到哈希表中，等待后续它匹配的那个值；
        //3-如果哈希表中有target-nums[i]的值，说明我们之前遍历的时候遍历到了，根据哈希表从中取出记录的位置；
        //4-注意所有的位置都是从1开始，要加1。
        int[] res = new int[2];
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if(map.containsKey(target-numbers[i]) ){
                res[0] = Math.min(i+1,map.get(target-numbers[i]));
                res[1] = Math.max(i+1,map.get(target-numbers[i]));
                return res;
            }else{
                map.put(numbers[i],i+1);
            }
        }
        return res;
    }
}
